pub fn dp_rec_mc(amount: u32) -> u32 {
    let n = 7;
    let a = vec![0, 1, 2, 5, 10, 20, 50, 100];
    let w: usize = amount as usize;
    let mut dp: Vec<i32> = vec![-1; 300];
    dp[0] = 0;
    for i in 1..=n {
        for j in a[i]..=w {
            // println!("j={:?}",j);
            if dp[j-a[i]] != -1 {
                if dp[j] == -1 {
                    dp[j] = dp[j-a[i]] + 1;
                    // println!("dp[{:?}]({:?}) = dp[{:?}]({:?}) + 1",j, dp[j], j-a[i], dp[j-a[i]]);
                }
                else {
                    dp[j] = dp[j].min(dp[j-a[i]] + 1);
                }
            }
        }
        // for k in 0..=w {
        //     print!("{} ", dp[k]);
        // }
        // println!("");
    }
    dp[w] as u32
}
